package com.zdb.datastructures.sort;

import com.zdb.datastructures.utils.MockDataUtils;
import com.zdb.datastructures.utils.TimeUtils;

import java.util.Arrays;

public class InsertionSort {

    public static void main(String[] args) {
//        int[] arr = {101, 34, 119, 1};
        int[] arr = MockDataUtils.mock80000IntArr();
        TimeUtils.printNowStr();
        insertionSort(arr);
        TimeUtils.printNowStr();
    }
    
    public static void insertionSort(int[] arr) {

        for(int j=0; j<arr.length-1; j++) {
            int insertVal = arr[j + 1];
            int insertIdx = j + 1;

            while (insertIdx > 0 && insertVal < arr[insertIdx-1]) {
                arr[insertIdx] = arr[insertIdx - 1];
                insertIdx -= 1;
            }
            // 插入当前位置
            arr[insertIdx] = insertVal;
//            System.out.println("第" + (j + 1) + "次排序，=" + Arrays.toString(arr));
        }

    }
}
